package _11_整理题目._7_查找排序._0_二分查找;

import org.junit.Test;

/**
 * 有序数组，无重复元素，找到指定元素返回数组下标，否则返回 -1
 *
 * 二分查找 易混淆代码部分
 *      1、while (left <= right)
 *          <= 的终止条件是 [3, 2]
 *          <  的终止条件是 [2, 2] 2 会被遗漏，需要补丁
 *      2、right = nums.length-1  表示的是 []
 *         right = nums.length   表示的是 [)
 *
 */
public class _01_普通二分查找 {
    
    public int binarySearch(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right-left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    
    @Test
    public void main() {
        int[] input = {1, 22, 37, 42, 63, 88, 99};
        System.out.println(binarySearch(input, 42));
        assert binarySearch(input, 42) == 3;


    }
}
